package Queue;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 *  题目 ：根据身高来重构队列
 *  题目详述 ：
 *  假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。
 *  每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
 *
 *  请你重新构造并返回输入数组people 所表示的队列。
 *  返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
 */
public class LengthToQueue {
    /**
     * 核心思想 ：
     * 渔（套路）：
     *   一般这种数对，还涉及排序的，
     *   根据第一个元素正向排序，根据第二个元素反向排序，
     *   或者根据第一个元素反向排序，根据第二个元素正向排序，往往能够简化解题过程
     */

    /**
     *  方法一 ：从高到低进行考虑
     *  即，将people二维数组按照第一关键字（身高）进行降序排序，同时根据第二关键字（之前队列中身高大于等于自身身高的数目）
     *  解析 :
     *  即，由于根据身高进行排序，
     *  所以后续数组元素插入队列时，无论其插入在队列中哪个为止对于之前的元素都没有影响（因为其身高必然小于或者等于前面的元素）；
     *  根据此规律，可以将排序好的数组元素依次插入；
     *  以此插入时，由于数组元素也是根据第二关键字进行升序排序，
     *  所以队列还是满足 ：所要插入元素所对应的队列中的位置之前的元素必然是大于等于其自身；
     *
     *  ===》
     *  结论 ：
     *  （1）先对于输入的数组，根据第一关键字升高进行降序排序；同时根据第二关键字（之前队列中身高大于等于自身身高的数目）进行升序排序
     *  （2）依次向队列中插入排序好数组中的元素，根据其第二关键字来决定其所需要插入的位置；
     * @param people
     * @return
     */
    public int[][] reconstructQueue(int[][] people) {
        // 对于数组进行排序（根据第一关键字降序排序，同时根据第二关键字升序排序）
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
//                if(o1[0] == o2[0]){
//                    return o1[1] - o2[1]; // 在第一关键字相同的情况下，根据第二关键字，进行升序排序；
//                }
//                else {
//                    return o2[0] - o1[0];// 根据第一关键字，进行降序排序；
//                }

                return  o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
                /**
                 * 注意 ：
                 * Arrays.sort方法详解 :
                 * 默认排序规则为 升序排序；
                 * 若是需要去自定义排序规则，则需要去重写compare方法，自定义比较规则
                 *
                 * 重写方法 ：
                 *  @Override
                 *  public int compare(int[] o1, int[] o2)
                 *
                 *  重点 ：  new Comparator<int[]>()
                 *  return  o1[0] - o2[0] : 即，为升序排列；
                 *  return  o2[0] - o1[0] : 即，为降序排列
                 */
            }
        });

        // 依次将数组中元素，根据第二关键字逐步地去插入队列中
        // 使用集合来模拟队列形式
        List<int[]> queue = new ArrayList<>();
        for (int[] person : people) { // 遍历整个people数组；
            queue.add(person[1] , person);
            // 索引 ：根据数组中每个元素的第二关键字作为集合中的索引，插入队列中所对应的位置；
            // 集合所存储的即时people数组中的各个数据
        }

        // 调用list.toArray方法，将集合转化为数组
        // 注意 ：list.toArray方法中的参数 ： 即为所要转化为的数组类型（二维数组）
        return queue.toArray(new int[queue.size()][]);
    }
}
